package sort

/**
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。
但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
这样一来，当遍历完未排序区间，就意味着已经完成整个序列的排序了
动态图：https://visualgo.net/zh/sorting

时间复杂度：时间复杂度是O(n^2)；
空间复杂度：没有额外的存储空间，是原地排序算法；
算法稳定性：由于涉及非相邻元素的位置交换，所以是不稳定的排序算法。

综合比较前面介绍的三种排序算法，时间复杂度都是一样的，也都是原地排序，但是选择排序是不稳定的排序算法，
此外，插入排序和冒泡排序相比较的话，插入排序只需要执行一条语句，而冒泡排序需要三条，
因此在同等条件下，或者数据量很大的情况下，插入排序性能是要略优于冒泡排序的，
所以综合比较下来，三者的优先级是插入排序 > 冒泡排序 >> 选择排序。
 */
func selectionSort(nums []int) {
	if len(nums) <= 1 {
		return
	}
	// 已排序区间初始化为空，未排序区间初始化待排序切片
	for i := 0; i < len(nums); i++ {
		// 未排序区间最小值初始化为第一个元素
		min := i
		// 从未排序区间第二个元素开始遍历，直到找到最小值
		for j := i + 1; j < len(nums); j++ {
			if nums[j] < nums[min] {
				min = j
			}
		}
		// 将最小值与未排序区间第一个元素互换位置（等价于放到已排序区间最后一个位置）
		if min != i {
			nums[i],nums[min] = nums[min], nums[i]
		}
	}
}
